package MergeTwoOrderedArrays;

class Solution {


    /*解题思路如下：

1. 给定的两个数组 `nums1` 和 `nums2` 都是非递减有序的，这意味着最大的元素位于数组的末尾。因此，我们可以从数组的末尾开始合并它们，从后向前比较元素。

2. 初始化三个指针：
   - `index1` 指向 `nums1` 中最后一个有效元素的位置（即 `m-1`）。
   - `index2` 指向 `nums2` 中最后一个有效元素的位置（即 `n-1`）。
   - `mergedIndex` 指向合并后数组的最后一个位置（即 `m+n-1`）。

3. 开始合并过程：
   - 从 `index1` 和 `index2` 指向的位置开始，比较 `nums1[index1]` 和 `nums2[index2]` 的大小。
   - 如果 `nums1[index1]` 大于 `nums2[index2]`，则将 `nums1[index1]` 放入合并后数组的末尾，并将 `index1` 和 `mergedIndex` 向前移动。
   - 如果 `nums2[index2]` 大于等于 `nums1[index1]`，则将 `nums2[index2]` 放入合并后数组的末尾，并将 `index2` 和 `mergedIndex` 向前移动。
   - 这个过程不断重复，直到其中一个数组的所有元素都被合并为止。

4. 如果此时仍然存在未合并的元素，只需将它们按顺序放入合并后数组的头部（因为它们已经是有序的）。

5. 最终，合并后的结果存储在 `nums1` 数组中，而 `nums2` 数组中的元素被全部合并到 `nums1` 中，并按非递减顺序排列。

这个算法的时间复杂度为 O(m + n)，其中 m 和 n 分别是 `nums1` 和 `nums2` 的长度。由于是原地合并，所以不需要额外的空间，结果直接存储在 `nums1` 中。*/
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int index1 = m - 1; // 指向 nums1 中最后一个有效元素的位置
        int index2 = n - 1; // 指向 nums2 中最后一个有效元素的位置
        int mergedIndex = m + n - 1; // 指向合并后数组的最后一个位置

        // 从后向前比较元素，合并数组
        while (index1 >= 0 && index2 >= 0) {
            if (nums1[index1] > nums2[index2]) {
                nums1[mergedIndex] = nums1[index1]; // 较大元素放入合并后数组的末尾
                index1--; // 向前移动 index1
            } else {
                nums1[mergedIndex] = nums2[index2]; // 较大元素放入合并后数组的末尾
                index2--; // 向前移动 index2
            }
            mergedIndex--; // 向前移动 mergedIndex
        }

        // 如果 nums2 中还有元素未合并
        while (index2 >= 0) {
            nums1[mergedIndex] = nums2[index2]; // 将 nums2 中未合并的元素放入合并后数组的末尾
            index2--; // 向前移动 index2
            mergedIndex--; // 向前移动 mergedIndex
        }
    }
}
